package com.future;

import java.util.LinkedList;

/**
 * Description: ��ϵ���22�ڿ� Code02_MinCoinsNoLimit.java
 * ����һ���������� coins ����ʾ��ͬ����Ӳ�ң��Լ�һ������ amount ����ʾ�ܽ�
 * <p>
 * ���㲢���ؿ��Դճ��ܽ������� ���ٵ�Ӳ�Ҹ��� �����û���κ�һ��Ӳ�����������ܽ�����?-1 ��
 * <p>
 * �������Ϊÿ��Ӳ�ҵ����������޵ġ�
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/coin-change
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/11 17:45
 */
public class Solution_322 {

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
       /* coins = new int[]{411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422};
        amount = 9864;
        coins = new int[]{2};
        amount = 3;*/

        System.out.println(coinChange(coins, amount));
        System.out.println(coinChange_v2(coins, amount));
        System.out.println(coinChange_dp(coins, amount));
    }

    // =======================������ ��̬�滮 �ɲο��ڶ�������=======================
    public static int coinChange_dp(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }
        int N = coins.length;
        int[][] dp = new int[N + 1][amount + 1];
        for (int rest = 1; rest <= amount; rest++) {
            /**
             * rest���ɻ�ʣ�¶����ܴչ�amount
             * ��Ȼ ��rest=0ʱ��dp[N][0]=0��Ĭ��ֵ�ˣ�����Ҫ�ص�ȥ��ֵ
             */
            dp[N][rest] = Integer.MAX_VALUE;
        }
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= amount; rest++) {
                int ans = Integer.MAX_VALUE;
                for (int zhang = 0; zhang * coins[index] <= rest; zhang++) {
                    int a = dp[index + 1][rest - coins[index] * zhang];
                    if (a != Integer.MAX_VALUE) {
                        ans = Math.min(ans, zhang + a);
                    }
                }
                dp[index][rest] = ans;
            }
        }
        return dp[0][amount] == Integer.MAX_VALUE ? -1 : dp[0][amount];
    }

    // =======================��һ��=======================

    /**
     * ����
     * ��ʱ
     *
     * @param coins
     * @param amount
     * @return
     */
    public static int coinChange(int[] coins, int amount) {
        if (coins == null || coins.length == 0 || amount < 0) {
            return -1;
        }
        int ans = process(coins, 0, amount, new LinkedList<>());
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private static int process(int[] coins, int index, int rest, LinkedList<Integer> list) {
        int ans = Integer.MAX_VALUE;
        if (index == coins.length) {
            if (rest == 0) {
                ans = 0;
                for (Integer a : list) {
                    ans += a;
                }
            }
            return ans;
        }
        for (int zhang = 0; zhang * coins[index] <= rest; zhang++) {
            list.addLast(zhang);
            int a = process(coins, index + 1, rest - coins[index] * zhang, list);
            ans = Math.min(ans, a);
            list.removeLast();
        }
        return ans;
    }

    // ======================�ڶ��� coinChange������========================
    public static int coinChange_v2(int[] arr, int aim) {
        return process_v2(arr, 0, aim);
    }

    /**
     * arr[index...]��ֵ��ÿ����ֵ��������ѡ��
     * ���rest������ô��Ǯ��������С����
     * ��Integer.MAX_VALUE�����ô���㶨����
     *
     * @param arr
     * @param index
     * @param rest
     * @return
     */
    public static int process_v2(int[] arr, int index, int rest) {
        if (index == arr.length) {
            /**
             * �������һ������һλ����Чλ�ã���
             * ���rest=0��˵��������һ�ַ����ܴչ�amount
             * ���Ǵ�ʱʱ��Чλ�ã����Է���0�����򷵻����������
             * ��Ϊ���������Ѿ�����һ��������
             */
            return rest == 0 ? 0 : Integer.MAX_VALUE;
        }
        int ans = Integer.MAX_VALUE;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            // ע�⣺����������+zhang,���������Ϊnext=MAX�����
            int next = process_v2(arr, index + 1, rest - zhang * arr[index]);
            if (next != Integer.MAX_VALUE) {
                /**
                 * ˵�������amount��һ�ַ���
                 */
                ans = Math.min(ans, zhang + next);
            }
        }
        return ans;
    }


}
